This invention relates in general to digital signal processing and more specifically to frequency-domain scaling in discrete cosine transform applications.
Frequency-domain transforms are a valuable operation in many computer processing applications. Common transforms include Fourier Transform (FT), Discrete Fourier Transform (DFT), Fast Fourier Transform (FFT), Discrete Cosine Transform (DCT), Modified DCT (MDCT), etc. Such transforms, and techniques for implementing the transforms, are shown, e.g., in “The Transform and Data Compression Handbook,” Rao, K. R. and Yip, P. C., CRC Press, New York, 2000; and in “The quick Fourier transform: a FFT based on Symmetries,” Guo, H.; Sitton, G. A. and Burrus, C. S.; IEEE Trans. on Signal Processing, Vol. 46, No. 2, 1998.
The DCT is used extensively in audio and image processing. For example, many compression standards such as Joint Photographic Expert's Group (JPEG) and Motion Picture Experts Group (MPEG) use the DCT at the heart of their processing.
A problem with implementing frequency-domain transforms in digital processing systems is that the operations to compute the transform, and inverse transform, can be complex. Often, the accurate calculation of the transform requires performing high-precision multiplication and addition on many values. For example, there may be many hundreds of thousands, millions, or more, pixels in a single frame of an image. Frames of an image may be required to be processed at rates of, e.g., 24, 30 or 60 frames per second. The transforms may be required to operate in real time on the frames of pixels values. Thus, any small improvement in speed, precision or efficiency of the low-level transform calculations can often lead to a tremendous improvement in the overall processing. Such improvements can result in a higher-quality image given a fixed set of resources such as processing power and memory, in a device such as a consumer electronic playback system for audio and/or video.
Four traditional types of DCTs are referred to as DCT-I, DCT-II, DCT-III and DCT-IV, as defined in the equations, below. These four types can be calculated via one another. For example, an N-point DCT-II could be decomposed into N/2-point DCT-I and N/2-point DCT II, the later could be further discomposed until not any multiplication is needed. In image processing a two-dimensional DCT is used. The two-dimensional DCT can be obtained by performing multiple 1-dimensional DCTs with proper matrix transpositions. Other transforms can be achieved with the DCTs shown below. For example, a DFT could be implemented by DCT-I.
                    DCT        ⁢                  -                ⁢        I        ⁢                  :                                                                                          DCT            ⁡                          (                              k                ,                                  N                  +                  1                                ,                x                            )                                =                                    ∑                              n                =                0                            N                        ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              cos                ⁡                                  (                                                            π                      ⁢                                                                                          ⁢                      n                      ⁢                                                                                          ⁢                      k                                        N                                    )                                            ⁢                                                          ⁢                              (                                                      k                    =                    0                                    ,                  1                  ,                  2                  ,                                      …                    ⁢                                                                                  ⁢                    N                                                  )                                                    ;                            (        1        )                                DCT        ⁢                  -                ⁢        II        ⁢                  :                                                                                          DCT            ⁡                          (                              k                ,                N                ,                x                            )                                =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              cos                ⁡                                  (                                                                                    π                        ⁡                                                  (                                                                                    2                              ⁢                                                                                                                          ⁢                              n                                                        +                            1                                                    )                                                                    ⁢                                                                                          ⁢                      k                                                              2                      ⁢                      N                                                        )                                            ⁢                                                          ⁢                              (                                                      k                    =                    0                                    ,                  1                  ,                  2                  ,                                                            …                      ⁢                                                                                          ⁢                      N                                        -                    1                                                  )                                                    ;                            (        2        )                                DCT        ⁢                  -                ⁢        III        ⁢                  :                                                                                          DCT            ⁡                          (                              k                ,                N                ,                x                            )                                =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              cos                ⁡                                  (                                                            π                      ⁢                                                                                          ⁢                                              n                        ⁡                                                  (                                                                                    2                              ⁢                                                                                                                          ⁢                              k                                                        +                            1                                                    )                                                                                                            2                      ⁢                      N                                                        )                                            ⁢                                                          ⁢                              (                                                      k                    =                    0                                    ,                  1                  ,                  2                  ,                                                            …                      ⁢                                                                                          ⁢                      N                                        -                    1                                                  )                                                    ;                            (        3        )                                DCT        ⁢                  -                ⁢        IV        ⁢                  :                                                                                          DCT            ⁡                          (                              k                ,                N                ,                x                            )                                =                                    ∑                              n                =                0                                            N                -                1                                      ⁢                                          x                ⁡                                  (                  n                  )                                            ⁢                              cos                ⁡                                  (                                                                                    π                        ⁡                                                  (                                                                                    2                              ⁢                                                                                                                          ⁢                              n                                                        +                            1                                                    )                                                                    ⁢                                              (                                                                              2                            ⁢                                                                                                                  ⁢                            k                                                    +                          1                                                )                                                                                    4                      ⁢                      N                                                        )                                            ⁢                                                          ⁢                              (                                                      k                    =                    0                                    ,                  1                  ,                  2                  ,                                                            …                      ⁢                                                                                          ⁢                      N                                        -                    1                                                  )                                                    ;                            (        4        )            where x(n) is the time-domain sequence.
The prior art has many different approaches and optimization techniques for DCT processing. FIG. 1, shows a typical approach using decomposition. In FIG. 1, flowchart 10 illustrates basic steps in a process whereby a time-domain signal is decomposed, subjected to 2-point DCT and then composed to produce a full DCT transform.
Flowchart 10 of FIG. 1 is entered at step 12. At step 14, the time-domain sequence, x(n) (e.g., a function describing picture element values in an image, audio waveform sample values, etc.), is a discrete function of N points. Since it is desirable to perform a DCT on two points at a time, the N point sequence is successively “decomposed” into sequences of length Ni until Ni=2. This is shown by step 18 which performs the decomposition to result in x^(n) having a lesser sequence. A check is made at step 20 to determine whether the decomposed sequence is of length 2. If not, the decomposition step is repeated until sequences of length 2 are attained.
Next, at step 30, two-point DCTs are performed to yield x′(k), where k represents a frequency band and the value of x^(k) represents the magnitude, or power, of the frequency band, as is known in the art. Steps 32, 34 and 36 perform a composition of the 2-point DCTs to build up the resulting frequency-domain function x(k) to a function, or sequence, of N coefficients. Thus, step 34 successively performs a composition function on the results of the 2-point DCT to yield x′(k) as shown at 32. For each iteration of the composition step, a larger set of coefficients, Ni, is attained. At step 36 a check is made as to whether Ni=N. If not, composition is continued.
When Ni=N at step 36 the result is an N coefficient DCT, x(k) and the transform terminates at step 40.
One drawback of the prior art approaches is that scaling of parameters is typically performed in the time-domain at decomposition step 18. The factor
  1      2    ⁢          cos      ⁡              (                              π            ⁢                                                  ⁢            n                    N                )            is used to scale coefficients in the time-domain sequence. Since this factor results in very large values it is difficult to represent the factor, and subsequent operations with the factor, efficiently in the binary arithmetic that is used in digital processors. When the word size of a central processing unit (CPU) is limited the handling of small fractional numbers with a high degree of precision can require double-width, or larger, representations and slower floating point arithmetic operations. Truncating or rounding the values loses precision and degrades the accuracy of the transform. The introduction of a large scale factor at step 18 and 16 of FIG. 1 also means that the effects of the large number representations are propagated to subsequent steps in the calculations. Other effects from time-domain scaling approaches of the prior art can include increased memory requirements and larger bandwidth for data transfers within a processing system.